package Tree;

public class leet_236 {
}


class Solution_236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归判断是否到底
        if(root==null){
            return null;
        }
        // 跳出递归
        if(root==p || root==q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 四种情况

        if(left!=null && right!=null){
            // 1.如果 左子树与右子树均不为空
            // 代表p与q分布在2侧所以直接输出结点
            return root;
        }else if(left!=null && right==null){
            // 若右子树为空 那么p q结点只会存在 left这一侧
            return left;
        }else if(right!=null && left==null){
            // 若左子树为空 那么p q结点只会存在 right这一侧
            return right;
        }

        // 那就代表2个都为空代表都没有祖先结点
        return null;
    }


}